{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Concatenated Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitLoopedString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割连接字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串列表&nbsp;<code>strs</code>，你可以将这些字符串连接成一个循环字符串，对于每个字符串，你可以选择是否翻转它。在所有可能的循环字符串中，你需要分割循环字符串（这将使循环字符串变成一个常规的字符串），然后找到字典序最大的字符串。</p>\n",
    "\n",
    "<p>具体来说，要找到字典序最大的字符串，你需要经历两个阶段：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>将所有字符串连接成一个循环字符串，你可以选择是否翻转某些字符串，并按照给定的顺序连接它们。</li>\n",
    "\t<li>在循环字符串的某个位置分割它，这将使循环字符串从分割点变成一个常规的字符串。</li>\n",
    "</ol>\n",
    "\n",
    "<p>你的工作是在所有可能的常规字符串中找到字典序最大的一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> strs = [\"abc\",\"xyz\"]\n",
    "<strong>输出:</strong> \"zyxcba\"\n",
    "<strong>解释:</strong> 你可以得到循环字符串 \"-abcxyz-\", \"-abczyx-\", \"-cbaxyz-\", \"-cbazyx-\"，其中 '-' 代表循环状态。 \n",
    "答案字符串来自第四个循环字符串， 你可以从中间字符 'a' 分割开然后得到 \"zyxcba\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> strs = [\"abc\"]\n",
    "<strong>输出:</strong> \"cba\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= strs.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= strs[i].length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= sum(strs[i].length) &lt;= 1000</code></li>\n",
    "\t<li><code>strs[i]</code>&nbsp;只包含小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-concatenated-strings](https://leetcode.cn/problems/split-concatenated-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-concatenated-strings](https://leetcode.cn/problems/split-concatenated-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abc\",\"xyz\"]', '[\"abc\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "        arr = []\n",
    "        for x in strs:\n",
    "            arr.append(max(x, x[::-1]))\n",
    "        ans = ''.join(arr)\n",
    "        ## 枚举起点\n",
    "        for i, s in enumerate(arr):\n",
    "            tmp = ''.join(arr[i+1:]) + ''.join(arr[:i])\n",
    "            for j, x in enumerate(s):\n",
    "                head = s[j:]\n",
    "                tail = s[:j]\n",
    "                ans = max(ans, head + tmp + tail)\n",
    "                ans = max(ans, tail[::-1] + tmp + head[::-1])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "        strs = [s[::-1] if s[::-1] > s else s for s in strs]\n",
    "        ans = ''.join(strs)\n",
    "        for i, s in enumerate(strs):\n",
    "            other = ''.join(strs[i + 1:]) + ''.join(strs[: i])\n",
    "            for j, _ in enumerate(s):\n",
    "                head = s[j:]\n",
    "                tail = s[: j]\n",
    "                cur = head + other + tail\n",
    "                ans = max(ans, cur)\n",
    "                cur = tail[::-1] + other + head[::-1]\n",
    "                ans = max(ans, cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "        strs=[ s[::-1] if s[::-1]>s else s for s in strs]\n",
    "        ret=''.join(strs)\n",
    "        # Suppose cur from strs[i]\n",
    "        for i, s in enumerate(strs):\n",
    "            other=''.join(strs[i+1:])+''.join(strs[0:i])\n",
    "            for j,_ in enumerate(s):\n",
    "                # s is in order\n",
    "                prefix=s[j:]\n",
    "                tail=s[:j]\n",
    "                cur=prefix+other+tail\n",
    "                ret=max(ret,cur)\n",
    "                # s is in disorder\n",
    "                cur=tail[::-1]+other+prefix[::-1]\n",
    "                ret=max(ret,cur)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "        strs = [max(x,x[::-1]) for x in strs]\n",
    "        ans = ''.join(strs)\n",
    "        for i,w in enumerate(strs):\n",
    "            mid = ''.join(strs[i + 1:]) + ''.join(strs[:i])\n",
    "            for x in [w,w[::-1]]:\n",
    "                for j in range(len(x)):\n",
    "                    head,tail = x[j:],x[:j]\n",
    "                    ans = max(ans,head + mid + tail)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "        strs = [s[::-1] if s[::-1] > s else s for s in strs]\n",
    "        ans = ''.join(strs)\n",
    "        for i, s in enumerate(strs):\n",
    "            other = ''.join(strs[i + 1:]) + ''.join(strs[: i])\n",
    "            for j, _ in enumerate(s):\n",
    "                head = s[j:]\n",
    "                tail = s[: j]\n",
    "                cur = head + other + tail\n",
    "                ans = max(ans, cur)\n",
    "                cur = tail[::-1] + other + head[::-1]\n",
    "                ans = max(ans, cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "\n",
    "        def strcmp(a,b):\n",
    "            #等长的\n",
    "            if a==b:\n",
    "                return 0\n",
    "            for x,y in zip(a,b):\n",
    "                if x==y:\n",
    "                    pass\n",
    "                elif x>y:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return -1\n",
    "            \n",
    "            return 0\n",
    "        N = len(strs)\n",
    "        for i in range(N):\n",
    "            s = strs[i]\n",
    "            if strcmp(s,s[::-1])<0:\n",
    "                strs[i]=s[::-1]\n",
    "        \n",
    "        #在中段一定是越大越好，开头不好说\n",
    "        print(strs)\n",
    "        max_line = ''.join(strs)\n",
    "        for i in range(len(strs)):\n",
    "            head = strs[i]\n",
    "            cur_rest = ''.join(strs[i+1:]) + ''.join(strs[:i])\n",
    "            for j in range(len(head)):\n",
    "                #以j的下标开头\n",
    "                cur_line = head[j:]+cur_rest+head[:j]\n",
    "                if strcmp(cur_line,max_line)==1:\n",
    "                    max_line = cur_line\n",
    "\n",
    "            #反过来也有可能\n",
    "            head = head[::-1]     \n",
    "            for j in range(len(head)):\n",
    "                #以j的下标开头\n",
    "                cur_line = head[j:]+cur_rest+head[:j]\n",
    "                if strcmp(cur_line,max_line)==1:\n",
    "                    max_line = cur_line   \n",
    "        return max_line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitLoopedString(self, strs: List[str]) -> str:\n",
    "        lenth=''.join(strs)\n",
    "        count=0\n",
    "        index_strs=0\n",
    "        ret=lenth\n",
    "        lenth=len(lenth)\n",
    "        for i in range(lenth):\n",
    "            this=''\n",
    "            count+=1\n",
    "            if count>len(strs[index_strs]):\n",
    "                count=1\n",
    "                index_strs+=1\n",
    "            temp=strs[index_strs]\n",
    "            temp_reverse=temp[::-1]\n",
    "            if temp[count-1:]>temp_reverse[count-1:]:\n",
    "                this=temp[count-1:]\n",
    "                fin=temp[:count-1]\n",
    "            else:\n",
    "                this=temp_reverse[count-1:]\n",
    "                fin=temp_reverse[:count-1]\n",
    "            for j in range(1,len(strs)):\n",
    "                temp=max(strs[(j+index_strs)%len(strs)][::-1],strs[(j+index_strs)%len(strs)])\n",
    "                this+=temp\n",
    "                if this<ret[:len(this)]:\n",
    "                    break\n",
    "            if this>ret:\n",
    "                this+=fin\n",
    "            ret=max(ret,this)\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
